package 记忆化搜索;

import java.util.Arrays;

//213 打家劫舍2
public class Solution2 {
    public int rob(int[] nums) {
        if(nums.length==1) return nums[0];
        dp = new int[nums.length];
        Arrays.fill(dp,-1);
        int res1 = dfs1(0,nums);
        Arrays.fill(dp,-1);
        int res2 = dfs2(1,nums);
        return Math.max(res1,res2);
    }
    int[] dp;
    //这里其实用一个dfs就可以了，只需要多一个传入的参数就行，来控制出口条件，比如index>=end，end在主方法里面传入不同的即可
    int dfs1(int index, int[]nums){
        if(index>=nums.length-1) return 0;
        if(dp[index]!=-1) return dp[index];
        return dp[index]=Math.max(dfs1(index+1,nums),dfs1(index+2,nums)+nums[index]);
    }
    int dfs2(int index, int[]nums){
        if(index>=nums.length) return 0;
        if(dp[index]!=-1) return dp[index];
        return dp[index]=Math.max(dfs2(index+1,nums),dfs2(index+2,nums)+nums[index]);
    }
}
